import java.util.Arrays;

/**
 * @program: leetcode031
 * @author: JCM
 * @create: 2022-11-28 20:50
 * @description: 下一个排列
 **/
public class LeetCode031 {

    /**
     * 思路：
     * [1,2,3,4,5] 的 下一个全排列就是 [1,2,3,5,4]
     * [5,4,7,5,3,2] 的 下一个全排列是 [5,5,2,3,4,7]
     * 通过观察发现，全排列后的结果是 右边的某一个数 例如 nums[j] 与 左边的某一个数 nums[i] 交换后，然后 下标i 后面的数字再从小到大排序的结果
     * 例如：[1,2,3,4,5] 的下一个全排列是 5(下标4) 和 4(下标3) 交换，然后下标 3 之后的数字从小到大排列的结果
     *      [5,4,7,5,3,2] 的 下一个全排列是  右5(下标3) 和 4(下标1) 交换，然后下标 1 之后的数字从小到大排列的结果
     * 寻找nums[i]和nums[j] 的方法：
     *      从右往左开始寻找，从倒数第二个数开始，将其记作 nums[i],然后在 nums[i] 的后面去寻找比 nums[i] 大的数, 并且将这些数进行比较，只
     *      保留下最小的并且大于 nums[i] 的下标。
     *  找到 nums[i] 和 nums[j] 之后，交换 nums[i] 和 nums[j]，然后对 下标i 后面的数字从下到大排序就可以了。
     *  特殊情况：
     *      当所给的全排列已经是最大的全排列时，则无法找到 nums[i] 和 nums[j], 此时只需要将数组从小到大排序完毕即可
     *      例如：[3,2,1] 的下一个全排列是 [1,2,3]
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        // 数组中的数少于两个，则无论如何排列都不变，直接返回即可
        if(nums.length<2) return;
        // min 用来保存比 nums[i] 大的最小值
        int min = 100;
        // index 用来记录 min 的下标
        int index = -1;
        // flag 用来判断是否已经找到所要找的两个数字
        boolean flag = false;
        // 从倒数第二个数开始遍历
        for(int i=nums.length-2; i >= 0; i--) {
            for(int j = nums.length-1; j > i; j--) {
                if(nums[j] > nums[i] && nums[j] < min) {
                    // 找到符合要求的数后，再做进一步的判定
                    min = nums[j];
                    index = j;
                    flag = true;// 更改 flag 的值，标志着已经找到了符合要求的两个数字。
                }
            }
            // 当 flag == true 时，进行交换和排序操作。
            if(flag) {
                swap(nums,i,index);
                Arrays.sort(nums,i+1,nums.length);
                // 全部步骤完成，直接退出循环
                break;
            }
        }
        // 如果找不到符合要求的数字，那么就对整个数组从小到大排序。
        if(!flag) {
            Arrays.sort(nums);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
